package com.atguigu.tree;

import java.util.*;

/**
 * 赫夫曼编码
 */
public class HuffmanCode {


    public static void main(String[] args) {
        String str = "i like like like java do you like a java";
        byte[] bytes = str.getBytes();
//        System.out.println(bytes.length);
//        List<HuNode> huNodes = strToList(bytes);
//        HuNode huNode = listToTree(huNodes);
//        huNode.preOrder();
//        System.out.println("打印赫夫曼编码对应的hashmap");
//        StringBuilder stringBuilder = new StringBuilder();
//        HashMap<Byte, String> byteStringHashMap = new HashMap<>();
//        hucodeToStr(huNode,stringBuilder,"",byteStringHashMap);
//        Set<Map.Entry<Byte, String>> entries = byteStringHashMap.entrySet();
//        for (Map.Entry<Byte, String> entry : entries) {
//            Byte key = entry.getKey();
//            String value = entry.getValue();
//            System.out.println(key+":"+value);
//        }
//
        byte[] bytes1 = byteToByte(bytes);
        System.out.println(bytes1.length);
        System.out.println(Arrays.toString(bytes1));
    }

    //将原始的字符串字节数组转成赫夫曼编码的字节数组
    public static byte[] byteToByte(byte[] bytes){
        System.out.println(bytes.length);
        List<HuNode> huNodes = strToList(bytes);
        HuNode huNode = listToTree(huNodes);
        StringBuilder stringBuilder = new StringBuilder();
        HashMap<Byte, String> byteStringHashMap = new HashMap<>();
        hucodeToStr(huNode,stringBuilder,"",byteStringHashMap);
        byte[] bytes1 = codeToArray(bytes, byteStringHashMap);
        return bytes1;
    }

    //赫夫曼编码转字节数组
    public static byte[] codeToArray(byte[] bytes,HashMap<Byte, String> codeHashMap){
        StringBuilder stringBuilder = new StringBuilder();
        for (byte aByte : bytes) {
            String s = codeHashMap.get(aByte);
            stringBuilder.append(s);
        }
        System.out.println(stringBuilder.toString());

        int length;
        if (stringBuilder.length() % 8 ==0){
            length = stringBuilder.length() / 8;
        }else {
            length = (stringBuilder.length() / 8) + 1 ;
        }

        byte[] bytes1 = new byte[length];
        int index =0;
        String substring = "";
        for (int i=0; i< stringBuilder.length();i+=8){

            if (i+8>= stringBuilder.length()){
                substring = stringBuilder.substring(i);
            }else {
                substring = stringBuilder.substring(i, i + 8);
            }

            bytes1[index] = (byte)Integer.parseInt(substring,2);
            index++;
        }

        return bytes1;
    }

    public static List<HuNode> strToList(byte[] bytes){
        ArrayList<HuNode> huNodes = new ArrayList<>();
        HashMap<Byte, Integer> integerIntegerHashMap = new HashMap<>();
        for (Byte aByte : bytes) {
            if (integerIntegerHashMap.get(aByte) == null){
                integerIntegerHashMap.put(aByte,1);
            }else {
                integerIntegerHashMap.put(aByte,integerIntegerHashMap.get(aByte)+1);
            }
        }

        Set<Map.Entry<Byte, Integer>> entries = integerIntegerHashMap.entrySet();

        for (Map.Entry<Byte, Integer> entry : entries) {
            Byte key = entry.getKey();
            Integer value = entry.getValue();
            HuNode huNode = new HuNode(value,key);
            huNodes.add(huNode);
        }

        return huNodes;
    }

    //生成赫夫曼树的方法
    public static HuNode listToTree(List<HuNode> node){

        while (node.size()>1){
            Collections.sort(node);
            HuNode leftNode = node.get(0);
            HuNode rightNode = node.get(1);
            HuNode huNode = new HuNode(leftNode.getVal() + rightNode.getVal(), null);
            huNode.setLeftNode(leftNode);
            huNode.setRightNode(rightNode);
            node.remove(leftNode);
            node.remove(rightNode);
            node.add(huNode);
        }
        return node.get(0);
    }

    //将赫夫曼树转为赫夫曼编码，左边为0，右边为1
    public static void hucodeToStr(HuNode node,StringBuilder strBuild,String str,HashMap<Byte,String> byteStringHashMap){

        StringBuilder stringBuilder = new StringBuilder(strBuild);
        stringBuilder.append(str);
        if (node.leftNode != null){
            if (node.leftNode.charCode == null){
                hucodeToStr(node.leftNode,stringBuilder,"0",byteStringHashMap);
            }else {
                stringBuilder.append("0");
                byteStringHashMap.put(node.leftNode.charCode,stringBuilder.toString());
            }

        }

        if (node.rightNode != null){
            if (node.rightNode.charCode == null){
                hucodeToStr(node.rightNode,stringBuilder,"1",byteStringHashMap);
            }else {
                stringBuilder.append("1");
                byteStringHashMap.put(node.rightNode.charCode,stringBuilder.toString());
            }

        }
    }



}

class HuNode implements Comparable<HuNode>{

    //出现次数
    int val;
    //字符值的ASCALL码十进制数
    Byte charCode;

    HuNode leftNode;
    HuNode rightNode;

    public HuNode(int val,Byte charCode){
        this.val = val;
        this.charCode = charCode;
    }

    public void preOrder(){
        System.out.println(this.charCode+":"+this.val);
        if (this.leftNode != null){
            this.leftNode.preOrder();
        }
        if (this.rightNode != null){
            this.rightNode.preOrder();
        }
    }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public int getCharCode() {
        return charCode;
    }

    public void setCharCode(Byte charCode) {
        this.charCode = charCode;
    }


    public void setLeftNode(HuNode leftNode) {
        this.leftNode = leftNode;
    }



    public void setRightNode(HuNode rightNode) {
        this.rightNode = rightNode;
    }

    @Override
    public String toString() {
        return "HuNode{" +
                "val=" + val +
                ", charCode=" + charCode +
                '}';
    }

    @Override
    public int compareTo(HuNode o) {
        return this.val - o.val;
    }
}
